package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC707 {
    public long startExecuteTime = System.currentTimeMillis();


    public class MyLinkedList {

        private class DoubleEndNode {
            public DoubleEndNode prev, next;
            public int val;

            public DoubleEndNode(int val) {
                this.val = val;
            }
        }

        private DoubleEndNode head;
        private DoubleEndNode tail;
        private int count;

        public MyLinkedList() {

        }

        public int get(int index) {
            if (index >= count) {
                return -1;
            }
            return getPos(index).val;
        }

        public void addAtHead(int val) {
            DoubleEndNode preHead = head;
            head = new DoubleEndNode(val);
            head.next = preHead;
            if (preHead != null) {
                preHead.prev = head;
            } else { // 旧的head是null代表原先没有任何元素
                tail = head;
            }
            count++;
        }

        public void addAtTail(int val) {
            DoubleEndNode preTail = tail;
            tail = new DoubleEndNode(val);
            tail.prev = preTail;
            if (preTail != null) {
                preTail.next = tail;
            } else { // 旧的tail是null代表原先没有任何元素
                head = tail;
            }
            count++;
        }

        private void insertAtFront(DoubleEndNode cur, int val) {
            DoubleEndNode newNode = new DoubleEndNode(val);
            newNode.next = cur;
            newNode.prev = cur.prev;
            cur.prev.next = newNode;
            cur.prev = newNode;
            count++;
        }

        private DoubleEndNode getPos(int index) {
            DoubleEndNode cur;
            if (index <= count / 2) {
                cur = head;
                while (index-- > 0) {
                    cur = cur.next;
                }
            } else {
                cur = tail;
                while (++index < count) {
                    cur = cur.prev;
                }
            }
            return cur;
        }

        public void addAtIndex(int index, int val) {
            if (index <= count) {
                if (index == count) {
                    addAtTail(val);
                } else if (index == 0) {
                    addAtHead(val);
                } else {
                    insertAtFront(getPos(index), val);
                }
            }
        }

        public void deleteAtIndex(int index) {
            if (index < count) {
                if (index == count - 1) {
                    if (count == 1) {
                        head = tail = null;
                    } else {
                        tail = tail.prev;
                        tail.next = null;
                    }
                } else if (index == 0) {
                    head = head.next;
                    head.prev = null;
                } else {
                    DoubleEndNode cur = getPos(index);
                    DoubleEndNode next = cur.next;
                    cur.prev.next = next;
                    next.prev = cur.prev;
                }
                count--;
            }
        }
    }


    public void run() {
        MyLinkedList solution = new MyLinkedList();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC707 an = new LC707();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
